<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>矩阵挖金子</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="矩阵挖金子">矩阵挖金子</h1>
<h1 id="1-走1次">1. 走1次</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=lBRtnuxg-gU&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=22">https://www.youtube.com/watch?v=lBRtnuxg-gU&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=22</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/MinCostPath.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/MinCostPath.java</a></li>
</ul>
<p>从左上角走到右下角， 只能往右走，或者往下走。  还是比较简单的。</p>
<h2 id="11-dp-from-bottom-to-top">1.1 dp from bottom to top</h2>
<pre><code class="language-java"><div>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">minCost</span><span class="hljs-params">(<span class="hljs-keyword">int</span> [][]cost,<span class="hljs-keyword">int</span> m,<span class="hljs-keyword">int</span> n)</span></span>{
        
        <span class="hljs-keyword">int</span> temp[][] = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[m+<span class="hljs-number">1</span>][n+<span class="hljs-number">1</span>];
        <span class="hljs-keyword">int</span> sum = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>; i &lt;= n; i++){
            temp[<span class="hljs-number">0</span>][i] = sum + cost[<span class="hljs-number">0</span>][i];
            sum = temp[<span class="hljs-number">0</span>][i];
        }
        sum = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>; i &lt;= m; i++){
            temp[i][<span class="hljs-number">0</span>] = sum + cost[i][<span class="hljs-number">0</span>];
            sum = temp[i][<span class="hljs-number">0</span>];
        }
        
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>; i &lt;= m; i++){
            <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">1</span>; j &lt;= n; j++){
                temp[i][j] = cost[i][j] + min(temp[i-<span class="hljs-number">1</span>][j-<span class="hljs-number">1</span>], temp[i-<span class="hljs-number">1</span>][j],temp[i][j-<span class="hljs-number">1</span>]);
            }
        }
        <span class="hljs-keyword">return</span> temp[m][n];
    }
</div></code></pre>
<h2 id="12-dfs-from-top-to-bottom">1.2 dfs from top to bottom</h2>
<pre><code class="language-java"><div>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">minCostRec</span><span class="hljs-params">(<span class="hljs-keyword">int</span> cost[][], <span class="hljs-keyword">int</span> m, <span class="hljs-keyword">int</span> n)</span></span>{
        <span class="hljs-keyword">return</span> minCostRec(cost, m, n, <span class="hljs-number">0</span> , <span class="hljs-number">0</span>);
    }
    
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">minCostRec</span><span class="hljs-params">(<span class="hljs-keyword">int</span> cost[][], <span class="hljs-keyword">int</span> m, <span class="hljs-keyword">int</span> n, <span class="hljs-keyword">int</span> x, <span class="hljs-keyword">int</span> y)</span></span>{
        <span class="hljs-keyword">if</span>(x &gt; m || y &gt; n){
            <span class="hljs-keyword">return</span> Integer.MAX_VALUE;
        }
        <span class="hljs-keyword">if</span>(x == m &amp;&amp; y == n){
            <span class="hljs-keyword">return</span> cost[m][n];
        }
        
        <span class="hljs-keyword">int</span> t1 = minCostRec(cost, m , n, x+<span class="hljs-number">1</span>, y);
        <span class="hljs-keyword">int</span> t2 = minCostRec(cost, m , n, x+<span class="hljs-number">1</span>, y+<span class="hljs-number">1</span>);
        <span class="hljs-keyword">int</span> t3 = minCostRec(cost, m , n, x, y+<span class="hljs-number">1</span>);
        
        <span class="hljs-keyword">return</span> cost[x][y] + min(t1,t2,t3);
    }
</div></code></pre>
<h1 id="2-走2次">2. 走2次</h1>
<p>leetcode 741. Cherry Pickup</p>
<p>这道题麻烦在于，要走2次， 从左上角走到右下角以后， 还要从右下角往左上角走回去。</p>
<pre><code><code><div>Share
In a N x N grid representing a field of cherries, each cell is one of three possible integers.

 
0 means the cell is empty, so you can pass through;
1 means the cell contains a cherry, that you can pick up and pass through;
-1 means the cell contains a thorn that blocks your way.


Example 1:

Input: grid =
[[0, 1, -1],
 [1, 0, -1],
 [1, 1,  1]]
Output: 5
Explanation: 
The player started at (0, 0) and went down, down, right right to reach (2, 2).
4 cherries were picked up during this single trip, and the matrix becomes [[0,1,-1],[0,0,-1],[0,0,0]].
Then, the player went left, up, up, left to return home, picking up one more cherry.
The total number of cherries picked up is 5, and this is the maximum possible.



</div></code></code></pre>
<p>The idea is to use self.memo[(i1, j1, i2, j2)] to store the maximum number of cherries that can be collected starting from (i1, j1) to (N-1, N-1) then to(i2, j2) . Note that since I'm taking a step at each end at the same time, i1+j1 is always equal to i2+j2, therefore there are only O(N^3) states (and I'm using the full quadruple to store the state for the sake of clearness).</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span><span class="hljs-params">(object)</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">cherryPickup</span><span class="hljs-params">(self, grid)</span>:</span>
        <span class="hljs-string">"""
        :type grid: List[List[int]]
        :rtype: int
        """</span>
        <span class="hljs-keyword">if</span> grid[<span class="hljs-number">-1</span>][<span class="hljs-number">-1</span>] == <span class="hljs-number">-1</span>: <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>
        
        <span class="hljs-comment"># set up cache</span>
        self.grid = grid
        self.memo = {}
        self.N = len(grid)
        
        <span class="hljs-keyword">return</span> max(self.dp(<span class="hljs-number">0</span>, <span class="hljs-number">0</span>, <span class="hljs-number">0</span>, <span class="hljs-number">0</span>), <span class="hljs-number">0</span>)
        
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">dp</span><span class="hljs-params">(self, i1, j1, i2, j2)</span>:</span>
        <span class="hljs-comment"># already stored: return </span>
        <span class="hljs-keyword">if</span> (i1, j1, i2, j2) <span class="hljs-keyword">in</span> self.memo: <span class="hljs-keyword">return</span> self.memo[(i1, j1, i2, j2)]
        
        <span class="hljs-comment"># end states: 1. out of grid 2. at the right bottom corner 3. hit a thorn</span>
        N = self.N
        <span class="hljs-keyword">if</span> i1 == N <span class="hljs-keyword">or</span> j1 == N <span class="hljs-keyword">or</span> i2 == N <span class="hljs-keyword">or</span> j2 == N: <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>
        <span class="hljs-keyword">if</span> i1 == N<span class="hljs-number">-1</span> <span class="hljs-keyword">and</span> j1 == N<span class="hljs-number">-1</span> <span class="hljs-keyword">and</span> i2 == N<span class="hljs-number">-1</span> <span class="hljs-keyword">and</span> j2 == N<span class="hljs-number">-1</span>: <span class="hljs-keyword">return</span> self.grid[<span class="hljs-number">-1</span>][<span class="hljs-number">-1</span>]
        <span class="hljs-keyword">if</span> self.grid[i1][j1] == <span class="hljs-number">-1</span> <span class="hljs-keyword">or</span> self.grid[i2][j2] == <span class="hljs-number">-1</span>: <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>
        
        <span class="hljs-comment"># now can take a step in two directions at each end, which amounts to 4 combinations in total</span>
        dd = self.dp(i1+<span class="hljs-number">1</span>, j1, i2+<span class="hljs-number">1</span>, j2)
        dr = self.dp(i1+<span class="hljs-number">1</span>, j1, i2, j2+<span class="hljs-number">1</span>)
        rd = self.dp(i1, j1+<span class="hljs-number">1</span>, i2+<span class="hljs-number">1</span>, j2)
        rr = self.dp(i1, j1+<span class="hljs-number">1</span>, i2, j2+<span class="hljs-number">1</span>)
        maxComb = max([dd, dr, rd, rr])
        
        <span class="hljs-comment"># find if there is a way to reach the end</span>
        <span class="hljs-keyword">if</span> maxComb == <span class="hljs-number">-1</span>:
            out = <span class="hljs-number">-1</span>
        <span class="hljs-keyword">else</span>:
            <span class="hljs-comment"># same cell, can only count this cell once</span>
            <span class="hljs-keyword">if</span> i1 == i2 <span class="hljs-keyword">and</span> j1 == j2:
                out = maxComb + self.grid[i1][j1]
            <span class="hljs-comment"># different cell, can collect both</span>
            <span class="hljs-keyword">else</span>:
                out = maxComb + self.grid[i1][j1] + self.grid[i2][j2]
                
        <span class="hljs-comment"># cache result</span>
        self.memo[(i1, j1, i2, j2)] = out
        <span class="hljs-keyword">return</span> out
</div></code></pre>

    </body>
    </html>